The present invention relates to a method and system for transmitting a program to a plurality of viewers, permitting flexible, nearly on demand viewing by an unlimited number of concurrent viewers, and, more particularly, to a method and system for transmission that minimizes transmission bandwidth, possibly subject to certain constraints.
Video-On-Demand (VOD) is the on-line version of traditional video-rental services. As with video rental services, each viewer receives a dedicated xe2x80x9ccopyxe2x80x9d of the movie and can view it in a flexible manner, including the ability to pause and resume, rewind, and possibly even fast-forward. With VOD, the xe2x80x9crentalxe2x80x9d operation is essentially instantaneous, and viewing can begin within seconds of the decision to view.
The xe2x80x9ccopyxe2x80x9d in VOD is a dedicated video stream. This stream is generated by a video server and sent to the viewer over a communication network. An important advantage of VOD over tape rental is the great flexibility in allocation of resources: the maximum number of concurrent viewers is independent of viewing choices, and is limited only by the server""s total streaming capacity. The required bandwidth resources, both in the server and in the communication network, are proportional to the number of concurrent viewers.
There are important situations in which a large number of people wish to view the same content during the same period of time, albeit not simultaneously. One example is viewing emergency-preparedness instruction in the hours or days prior to the arrival of a major storm. Another example is a newly released xe2x80x9chotxe2x80x9d movie that is advertised heavily. Yet another example is a movie whose viewing is assigned as homework, or even a recorded lecture viewed (individually) in class by the students. These pre-recorded instructions, movies and lectures are examples of programs that are to be viewed by many viewers, concurrently but not necessarily simultaneously.
Although VOD could be used to address such situations, it is both highly desirable and intuitively possible to do better. The desire stems from the fact that even the total (over all programs) number of concurrent viewers may be temporarily much higher than usual, so it would be very costly if not impossible to design the infrastructure (server and communication network) for such peaks. The intuition that something can be done arises from the observation that the many viewers of the xe2x80x9chotxe2x80x9d program are viewing the same material concurrently but not simultaneously. The various schemes for doing better than VOD in this situation are called xe2x80x9cNear Video On Demandxe2x80x9d. The goal of NVOD is to provide an unlimited number of viewers of the same program similar service flexibility to that of VOD at a reasonable cost to the server and communication network. Ideally, this cost is independent of the number of viewers. xe2x80x9cNearxe2x80x9d is defined to mean commencement of viewing within a reasonable time interval following viewer request, for example one minute in the case of a movie, as well as the ability to pause and resume at any time. Rewind and fast-forward functions are not obligatory.
There are two categories of NVOD systems: open-loop systems and closed-loop systems. In both systems, the viewers are provided with devices, called herein xe2x80x9cclientsxe2x80x9d because of their relationship with the server, that receive program copies transmitted by the server and display those copies to their respective viewers. In open-loop systems there is no feedback from the viewing client to the server, so neither server transmissions nor routing on the network are affected by viewer actions (other than the possible effect on routing due to a viewer joining a multicast group). Open-loop schemes lend themselves most naturally to broadcast-based networks, such as cable television networks, and even to networks that have only one-way communication, which is the common case in satellite-based information-dissemination networks. Closed-loop systems permit some feedback that allows the server to adjust to client requests throughout the viewing period. Note that the terms xe2x80x9cplayxe2x80x9d and xe2x80x9cdisplayxe2x80x9d are used interchangeably herein, to refer to the displaying of the received program by a client.
Recently, several open-loop NVOD schemes have been proposed. These schemes are based on partitioning the program into several segments, on the assumption that every client has a substantial amount of available storage capacity, for example on a hard disk, which can be used to temporarily store the segments. In such schemes, the server""s transmission schedule, and the algorithm used by the client to decide whether or not to record any given transmitted segment, jointly ensure that every segment of the movie is stored in the client""s recording medium by its viewing time.
One such scheme is taught by DeBey in U.S. Pat. No. 5,421,031, which is incorporated by reference for all purposes as if fully set forth herein. DeBey""s partitioning and scheduling scheme is illustrated in FIG. 1, for the case of segments of equal length. The vertical axis of FIG. 1 is segment number. The horizontal axis of FIG. 1 is the time at which a given segment is broadcast by the server, with the unit of time, as well as the basic time interval, being the duration of one segment. For each segment, the time during which that segment is broadcast by the server is represented by a double-headed arrow. The first segment is broadcast in every time interval, the second segment is broadcast every second time interval, the third segment is broadcast every third time interval, and in general the n-th segment is broadcast every n-th time interval. Note that all segments are transmitted at the same transmission rate of one segment per time interval. In addition, the transmissions continue throughout the time period during which the viewers are permitted to view the program.
A client that tunes in to the broadcast at the beginning of any time interval receives all the segments promptly enough to display the program with no interruptions. For example, a client that tunes in at the beginning of the seventh time interval, and that actually begins to display the movie to its viewer at the beginning of the eighth time interval, receives and records the seventh copy of the first segment during the seventh time interval, the fourth copy of the second segment during the eighth time interval, the third copy of the third segment during the ninth time interval, the second copy of the fourth segment during the eighth time interval, etc. In this case, the first segment is displayed during the eighth time interval, the second segment is displayed during the ninth time interval, the third segment is displayed during the tenth time interval, the fourth segment is displayed during the eleventh time interval, etc.
DeBey""s scheme imposes certain burdens on the server and on the clients. With N segments, the mean transmission bandwidth, in units of segments transmitted per time interval, is approximately ln(N); but the actual transmission bandwidth varies widely. For example, in prime-numbered time intervals after the first time interval, only two segments are broadcast, vs. e.g. six segments during the twelfth time interval. The client must be able to record the received segments fast enough to keep up with the peak aggregate transmission rate. Furthermore, the client must have enough storage capacity to store all recorded segments that are received too soon to play.
There is thus a widely recognized need for, and it would be highly advantageous to have, a NVOD method that imposes less of a burden on the resources available to the server and to the clients.
According to the present invention there is provided, in a system wherein a server transmits a program having a certain duration, the program being received by at least one client, a method for scheduling the transmission of the program, including the steps of: (a) partitioning the program into a plurality of sequential segments; (b) selecting a transmission rate for each segment, the transmission rate that is selected for a first the segment being faster than the transmission rate that is selected for any other the segment; and (c) transmitting the segments, by the server, each segment being transmitted at the transmission rate of the each segment.
According to the present invention there is provided a system for transmitting a program to a plurality of viewers, including: (a) a software module including a plurality of instructions for scheduling a transmission of the program by: (i) partitioning the program into a plurality of sequential segments, and (ii) selecting a transmission rate for each segment, the transmission rate that is selected for a first the segment being faster than the transmission rate that is selected for any other the segment; (b) a processor for executing the instructions; (c) a server for transmitting each segment at the respective transmission rate; and (d) for each viewer, a client for receiving the transmitted segments, recording the received segments and playing the recorded segments in the sequence.
According to the present invention there is provided, in a system wherein a server repeatedly transmits a program that is partitioned into a plurality of segments and wherein a client receives and records the segments and displays the program, the transmitting, receiving and recording of the segments being effected according to a schedule, a method for displaying the program intermittently, including the steps of: (a) transmitting, along with the segments, metadata describing the schedule, by the server; (b) pausing the display of the program, by the client; (c) resuming the display of the program, by the client, subsequent to the pausing; and (d) during the pausing, continuing to record at least a portion of the segments then received, by the client.
In its most basic embodiment, the present invention is a modification of the NVOD scheme of DeBey that smoothes out the instantaneous transmission bandwidth to always be close to the mean transmission bandwidth. This is accomplished by broadcasting all the segments concurrently, starting at the first time interval, but taking n time intervals to broadcast the n-th segment. In other words, if the first segment is transmitted at a transmission rate of T bits per unit time, then the n-th segment is transmitted at a transmission rate of T/n bits per unit time. This is illustrated in FIG. 2. Note that all transmissions end at the same times as in FIG. 1, but start at different times. Specifically, all the first transmissions of all the segments start at the beginning of the first time interval; and subsequently, as soon as the transmission of any segment ends, that segment is immediately retransmitted.
The simultaneous commencement shown in FIG. 2 is illustrative, and applies primarily to the basic embodiment illustrated therein. More generally, because the segments are transmitted repetitively and concurrently throughout the period during which the program is being offered to the viewers, the starting times of the transmission of different segments may be chosen at will.
The most basic embodiment of the present invention relieves the burden on the server, but not necessarily the burden on the clients. For example, a client that tunes in must receive and record all the data being transmitted until such time as it has finished recording a given segment and can cease recording the data for that segment. Thus, this client must be capable of receiving and recording data at a rate equal to the server""s aggregate transmission rate. Furthermore, towards the middle of the program, the client""s storage medium must have sufficient capacity to store a significant portion of the program even if the client discards the data of a segment once it is displayed. These stringent requirements may be relaxed if the start of the recording by a client of later segments is delayed long enough for earlier segments to be recorded, displayed and possibly even discarded, thus freeing up client resources to accommodate the later segments. Clearly, this implies an increase in the aggregate transmission rate, because a segment must be transmitted in its entirely during the time in which it is being recorded by the client; so that shortening this time without changing segment size mandates an increase in its transmission rate. In fact, the optimum overall system design is a tradeoff between minimizing the aggregate transmission rate and meeting client constraints such as limited recording rate and limited storage capacity. The ability to optimally design the system to optimize certain aspects of performance while adhering to constraints on others is a salient feature of the current invention. Algorithms for minimizing the aggregate transmission bandwidth subject to these constraints are presented in the Appendix.
More generally, the scope of the present invention includes NVOD methods and systems in which the first segment is transmitted at a higher transmission rate than the subsequent segments. Preferably, transmission rates of successive program segments are such that the latest time, measured from the time of a client""s viewing request, at which the client may begin to record a segment such that the recording of the segment is completed before that segment must be displayed, is no earlier for a later program segment than for an earlier one. It should be noted that this transmission rate of a segment is defined in terms of the overall transmission rate of the segment as a whole. For example, a server may use time division multiplexing to transmit all the segments concurrently on a single channel, by partitioning the segments into subsegments, interleaving the subsegments and transmitting all the subsegments at the same rate. Consider, for example, in the context of the most basic embodiment of the present invention, a case in which 100-second segments are partitioned into 1-second subsegments of B bits each, that are transmitted on a 1 gigabit-per-second channel. The duration of the transmission of each subsegment is Bxc3x9710xe2x88x929 seconds, no matter which segment is the source of the subsegment; but the 100 subsegments of the first segment are transmitted over the course of 100 seconds, for an overall transmission rate of B bits per second, whereas the 100 subsegments of the second segment are transmitted over the course of 200 seconds, for an overall transmission rate of B/2 bits per second.
It also is clear that a client may ignore, and not record, transmitted copies of any particular segment, until the transmission of the last such copy that is transmitted in its entirety before the segment must be displayed. To facilitate this, each transmitted copy of the segment includes metadata that describe various aspects of the segment, including, for example, the segment number, the size of the segment, the transmission rate of the segment, and a temporal value related to the time interval between the start of the transmission of this copy of the segment and the start of the transmission of the next copy of the segment. An example of this temporal value is the length of this time interval itself. Similarly, in an embodiment of the present invention in which the segments are partitioned into subsegments, each copy of a subsegment includes metadata that describe various aspects of the subsegment, including, for example, the number of the segment to which the subsegment belongs, the sequence number of the subsegment within its segment, the size of the subsegment, and a temporal value related to the time interval between the start of the transmission of this copy of the subsegment and the start of the transmission of the next copy of the subsegment.
When a segment is not partitioned into subsegments, the preferred embodiments of the current invention nonetheless include metadata that provides sufficient identification so as to permit the recording of the segment""s data to begin without waiting for the beginning of the segment. Similarly, when a segment is partitioned into subsegments, the metadata permits the subsegments to be recorded by the client in any order and to subsequently be assembled to form the original segment. Thus, the recording of a given segment by a client may commence essentially as late as one transmission time of the entire segment prior to the earliest time at which that segment may have to be displayed. The time to transmit the entire segment is, in turn, essentially equal to the size of the segment divided by the rate at which the segment is transmitted. Similarly, as soon as a segment is displayed, that segment may be deleted from the recording medium to free up the storage space occupied by that segment.
In one preferred embodiment of the present invention, the subsegments of at least one program segment are used to compute a larger number of such subsegments, such that the original segment can be derived from any sufficiently large subset of the subsegments; and all the subsegments are transmitted such that the time between successive transmissions of the same subsegment remains unchanged. This increases the transmission rate of the segment, but permits the use of error correcting codes to receive the segment successfully even in the event of communication problems.
In one application of the present invention, in order to allow a viewer to tune in to a broadcast of an entire live program after the program has started but before the program has ended, the basic embodiment of the present invention is initiated simultaneously with the live broadcast, with the repeated transmission of each segment initiated after the live transmission of that segment.
In some embodiments of the present invention, only one copy of each segment is stored at the server. In other embodiments of the present invention, multiple copies of the program data are stored at the server, to increase the efficiency of storage access when transmitting the program.
Optionally, the segments are encrypted and/or compressed by the server prior to transmission, and are decrypted and/or decompressed by each client prior to display.
A system of the present invention includes a software module that embodies the algorithm of the present invention, a processor for executing the instructions of the software module, and a server that includes both a data storage area for storing the program segments and a mechanism for transmitting the program segments according to the transmission rates assigned by the algorithm. Preferably, the software module and the processor also are included in the server; although it also is possible, within the scope of the present invention, for the server to obtain a rate allocation table or a transmission schedule from another device that includes the software module and the processor of the present invention and that operates off-line. The system also includes, for each viewer, a client for receiving, recording and displaying the segments, and a distribution network for broadcasting the segments to the clients.
The scope of the present invention also includes a method for pausing and resuming the display of the program by a client, whether the NVOD transmission rates are selected according to the teachings of the present invention or according to prior art schemes such as DeBey""s. Essentially, the client stops displaying the program, but continues to record incoming segments as though the program were being displayed at the point, in the program, where the display was temporarily stopped. To conserve the client""s storage space, metadata are transmitted along with the segments to indicate when the segments will be transmitted again, and segments that will be transmitted and recorded again before they need to be displayed, if displaying were to be resumed immediately, are discarded.